1. Field of the Invention
The present invention generally relates to a data search device that is provided in a communication apparatus and searches frame data stored in buffers. More particularly, the present invention relates to a data search device that is used in a gateway device that relays frame data to be transferred between at least two buses.
2. Description of the Related Art
When a gateway ECU (Electronic Control Unit) relays frame data to be transferred between at least two buses, it is possible to use a method for relaying frame data in order of reception, or a method for transmitting after leveling the frame data, regardless of the order of reception.
The “leveling” is to transmit in a uniform manner, regardless of the priority levels and transmission cycles of frame data. For example, in a case where frame data is consecutively received in order of A, B, C, A, D, E, A, B, C, A, D, E, . . . , the frame data is rearranged and transmitted in order of A, B, C, D, E, A, B, C, D, E, . . . .
By a known technique for leveling and transmitting frame data, a buffer is provided for each ID (IDentifier number) that identifies frame data, and frame data is read from the buffers in order of transmission. The IDs are allotted by a node (such as an ECU) located on the bus for transmitting the frame data. The IDs show the transmission source node and the priority levels of the frame data.
The buffers provided for the respective IDs are called ID-based buffers. For each area in the ID-based buffers, a flag that indicates whether data is stored in the corresponding area is recorded in a memory.
Each of the ID-based buffers is provided for each corresponding relay channel. For example, if the gateway ECU has two channels for relaying data, two ID-based buffers are provided.
When frame data is transmitted, a linear search is carried out on the flags provided for the respective areas in the ID-based buffers. Frame data is stored in the area in the ID-based buffers having a flag recorded therein (in an ON state). Accordingly, the frame data is read from the area in the ID-based buffers having the flag recorded therein, and is then transmitted.
Referring now to FIG. 1A, linear searches are described. In the first-time linear search, flags are searched from the top. In each of the second-time and later searches, however, a flag search is started from the buffer area next to the buffer area in which the previous search is ended. More specifically, in a case where the first-time search detects a flag recorded in an area of the seventh row (ID 192) from the top, as shown in FIG. 1A, the second-time search is started from the eighth row (ID 216). After the last area in the ID-based buffer is searched, the searching operation returns to the top and is repeated. If a buffer area having a flag set thereto is not found through the searching operation until the searching operation reaches the position where the search is started, the searching operation comes to an end there.
Japanese Unexamined Patent Publication No. 2005-159568 discloses a technique by which a RAM that determines beforehand the priority levels of ID codes representing transmission destinations is provided, and the transmission priority levels are determined based on the priority levels of the ID codes in the RAM if there are two or more sets of data to be next transmitted after data transmission.
Japanese Unexamined Patent Publication No. 2000-244548 aims to prevent data loss in a data relay device. According to Japanese Unexamined Patent Publication No. 2000-244548, a buffer that temporarily stores received data is provided for each type of data to be relayed, and a data controller that identifies the type of the received data and designates the buffer write destination in accordance with the data type is also provided.
However, if the number of buses between which data is relayed by a gateway ECU becomes larger, the time required for searches becomes longer, and the relay performance of the gateway ECU deteriorates.
For example, an ID-based buffer may be a buffer that can store 100 different IDs, as shown in FIG. 1B. To search the frame data stored in the 100th buffer area, it is necessary to carry out a search 100 times, starting from the top buffer area. Therefore, to maintain the high relay performance of the gateway ECU, it is necessary to prepare a high-performance CPU or restrict the number of buses between which data is relayed.
Furthermore, Japanese Unexamined Patent Publication Nos. 2005-159568 and 2000-244548 do not disclose any technique for improving the efficiency of searches to be carried out on the frame data stored in buffers.